In [ ]:
from functions import *

G. Explain which method you select to solve each of the problems and explain why.¶

All of the three problems were solved using the Hill Climber, Gradient descent with wolfe conditions and Newton Method. In general, the fastest method was the Newton Method and achieved more exact solutions, when there was no local minima. If the problem had local minima all of the methods got stuck in there (you could modify the ball radius of hill climber to get around this by seeing the graph and choosing a more optimal value, but this wouldn't be possible for black boxes problem).

H. Can evolutionary algorithms help to solve any of the previous problems? Why?¶

Evolutionary algorithms, such as Differential Evolution (DE), can help solve many of the previous optimization problems.

  1. Global Search Capability:

Differential Evolution is designed to explore the entire solution space, making it effective for finding global minima in functions that have multiple local minima. 2. No Need for Gradient Information: DE does not rely on gradient information, which is particularly useful when dealing with functions that are non-differentiable, noisy, or complex.

1. Classical optimization methods¶

F_A¶

Algorithm Point Found Evaluation Iterations Real Minimum Two Norm Error
Hill Climber [-0.0023754, 0.0010439] 1.30002043 600 1.30 0.0025946
Gradient Descent [0.0003116, 0.0004382] 1.3000001 50 1.30 0.0005378
Newton Method [0.0000000, 0.0000000] 1.3000000 1 1.30 7.64e-08

Hill Climber¶

In [ ]:
x_init = np.array([0.5,1])
constraints = [[-3, 3],[-2, 2]]
x_best, fx_best, x_history, fx_history = hill_climber(f_A, delta=0.1, n_iter=600, n_intervals=100, x_init=x_init, constraints = constraints)
print()
plot_function_with_paths(f_A, constraints, x_history, fx_history)
i = 600, x1 = -0.0023754, x2 = 0.0010439, fx_best = 1.30002043
No description has been provided for this image
True minimum found by differential evolution at x1 = -0.00, x2 = -0.00, with value = 1.30
Model minimum at x1 = -0.00, x2 = 0.00, with value = 1.30
L2 norm error for parameters: 0.0025946260183605913

Gradient Descent with Wolfe Conditions¶

In [ ]:
x_best, fx_best, x_history, fx_history, i = grad_descent(f_A, tol=0.0005, max_iter=100, n_intervals=8, x_init=x_init, constraints = constraints)
print()
plot_function_with_paths(f_A, constraints, x_history, fx_history)
i = 50, x1 = 0.0003116, x2 = 0.0004382, fx_best = 1.3000001
No description has been provided for this image
True minimum found by differential evolution at x1 = -0.00, x2 = -0.00, with value = 1.30
Model minimum at x1 = 0.00, x2 = 0.00, with value = 1.30
L2 norm error for parameters: 0.0005378301063052097

Newton Method¶

In [ ]:
x_best, fx_best, x_history, fx_history, i = newton_method(f_A, tol=0.0005, max_iter=100, n_intervals=6, x_init=x_init, constraints = constraints)
print()
plot_function_with_paths(f_A, constraints, x_history, fx_history)
i = 1, x1 = 0.0000000, x2 = 0.0000000, fx_best = 1.3000000
No description has been provided for this image
True minimum found by differential evolution at x1 = -0.00, x2 = -0.00, with value = 1.30
Model minimum at x1 = 0.00, x2 = 0.00, with value = 1.30
L2 norm error for parameters: 7.640523731205057e-08

F_B¶

Algorithm Point Found Evaluation Iterations Real Minimum Two Norm Error
Hill Climber [-1.7052825, 0.7924012] -0.2152794 300 -1.03 1.6174076
Gradient Descent [-1.7036022, 0.7960998] -0.2154638 17 -1.03 2.3436695
Newton Method [-1.7038120, 0.8000063] -0.2152910 27 -1.03 1.6163322

Hill Climber¶

In [ ]:
x_init=np.array([-4,4])
constraints = [[-6, 6],[-6, 6]]
x_best, fx_best, x_history, fx_history = hill_climber(f_B, delta=0.2, n_iter=300, n_intervals=50, x_init=x_init, constraints = constraints)
print()
plot_function_with_paths(f_B, constraints, x_history, fx_history)
i = 300, x1 = -1.7052825, x2 = 0.7924012, fx_best = -0.2152794
No description has been provided for this image
True minimum found by differential evolution at x1 = -0.09, x2 = 0.71, with value = -1.03
Model minimum at x1 = -1.71, x2 = 0.79, with value = -0.22
L2 norm error for parameters: 1.6174076087924738

Gradient Descent with Wolfe Conditions¶

In [ ]:
x_init=np.array([-4,4])
x_best, fx_best, x_history, fx_history, i = grad_descent(f_B, tol=0.0005, max_iter=100, n_intervals=1, x_init=x_init, constraints = constraints)
print()
plot_function_with_paths(f_B, constraints, x_history, fx_history)
i = 17, x1 = -1.7036022, x2 = 0.7960998, fx_best = -0.2154638
No description has been provided for this image
True minimum found by differential evolution at x1 = 0.09, x2 = -0.71, with value = -1.03
Model minimum at x1 = -1.70, x2 = 0.80, with value = -0.22
L2 norm error for parameters: 2.343669541364297

Newton Method¶

In [ ]:
x_init=np.array([-4,4])
x_best, fx_best, x_history, fx_history, i = newton_method(f_B, tol=0.0008, max_iter=50, n_intervals=5, x_init=x_init, constraints = constraints)
print()
plot_function_with_paths(f_B, constraints, x_history, fx_history)
i = 27, x1 = -1.7038120, x2 = 0.8000063, fx_best = -0.2152910
No description has been provided for this image
True minimum found by differential evolution at x1 = -0.09, x2 = 0.71, with value = -1.03
Model minimum at x1 = -1.70, x2 = 0.80, with value = -0.22
L2 norm error for parameters: 1.6163322504051563

F_C¶

Algorithm Point Found Evaluation Iterations Real Minimum Two Norm Error
Hill Climber [-1.9861292, 2.0028127] 7.9954832 500 0 2.8206325
Gradient Descent [-2, 2] 8 500 0 2.8284271
Newton Method [-2, 2] 8 150 0 2.8284271

Hill Climber¶

In [ ]:
x_init=np.array([-2,2])
x_best, fx_best, x_history, fx_history = hill_climber(f_C, delta=0.2, n_iter=500, x_init=x_init, constraints = constraints)
print()
plot_function_with_paths(f_C, constraints, x_history, fx_history)
i = 500, x1 = -1.9861292, x2 = 2.0028127, fx_best = 7.9954832
No description has been provided for this image
True minimum found by differential evolution at x1 = -0.00, x2 = -0.00, with value = 0.00
Model minimum at x1 = -1.99, x2 = 2.00, with value = 8.00
L2 norm error for parameters: 2.820632543626884

Gradient Descent with Wolfe Conditions¶

In [ ]:
x_init=np.array([-2,2])
x_best, fx_best, x_history, fx_history, i = grad_descent(f_C, tol=0.0005, max_iter=500, x_init=x_init,  constraints = constraints)
print()
plot_function_with_paths(f_C, constraints, x_history, fx_history)
i = 500, x1 = -2.0000000, x2 = 2.0000000, fx_best = 8.0000000
No description has been provided for this image
True minimum found by differential evolution at x1 = 0.00, x2 = 0.00, with value = 0.00
Model minimum at x1 = -2.00, x2 = 2.00, with value = 8.00
L2 norm error for parameters: 2.8284271244387718

Newton Method¶

In [ ]:
x_init=np.array([-2,2])
x_best, fx_best, x_history, fx_history, i = newton_method(f_C, tol=0.0005, max_iter=150, x_init=x_init, constraints = constraints)
print()
plot_function_with_paths(f_C, constraints, x_history, fx_history)
i = 150, x1 = -2.0000000, x2 = 2.0000000, fx_best = 8.0000000
No description has been provided for this image
True minimum found by differential evolution at x1 = 0.00, x2 = 0.00, with value = 0.00
Model minimum at x1 = -2.00, x2 = 2.00, with value = 8.00
L2 norm error for parameters: 2.8284271256217197